In data transmission over communication channels that are prone to errors, such as radio channels, error detection coding and/or error correction coding may be employed to reduce the errors in the data transmitted. The data transmitted is often digital information, which includes messages composed of binary bits of information, where each bit can have a value of either a ONE or a ZERO. Any given message is then a string comprising a number of ONES interspersed with a number of ZEROES. It will be appreciated that any string of L bits can represent one of 2.sup.L unique messages. The messages may represent digitized voice information or some other form of information.
Error detection coding and error correction coding may both be used in communication systems. A simple example of error detection coding is adding an identical copy of a message to that message, transmitting both, and performing a bit-by-bit comparison of the received message with the received copy. For each bit position, any disagreement between the message and a copy is evidence of a transmission error. The total number of disagreements for a message is a quantitative measure of the reliability of the data transmission. It will be appreciated that the total number of disagreements is an inexact measure of reliability because simultaneous errors at the same bit position in both the message and the copy are not recognized as disagreements.
A common error detection technique, the Cyclic Redundancy Check (CRC) technique, generates and adds to the message "check" bits that are determined based on the bits of the data message. The check bits constitute a "checkword" that is specific to a given message. The checkword may be appended to the message so that both are processed through the same encoder, both are transmitted through the communication channel together, and both are processed through the same decoder in the receiver. A CRC calculator in the receiver may then generate check bits corresponding to the decoded message bits that were received, and this receiver-calculated checkword may be compared with the decoded checkword that was received with the message. Any noncompliance indicates an error detected in transmission, and the degree of compliance may be used as a quantitative measure of the reliability of the data transmission. However, a problem with this error detection method in systems also using error correction coding is that the received message must complete error correction decoding before the error detection coding can be tested.
By way of contrast, a simple example of error correction coding is transmitting more than two identical copies of a given message and performing a bit-by-bit comparison of all messages received at the receiver. Whether a bit of the message output from the receiver should be a ONE or a ZERO may be decided on the basis of "bit democracy", i.e., the majority of the bit values received for that bit position determines the output. Transmission errors may be assumed to be randomly distributed among the message copies and will thus typically not occur at the same bit position in a majority of the copies.
A known error correction technique is convolutional coding, in which the bits transmitted, known as parity bits, are determined based on the message bits. The message bits are considered L bits at a time, and r parity bits are transmitted for every L message bits. For example, the parity bits may be calculated as certain Boolean combinations of various bits of the message. The transmission of convolutionally encoded parity bits distinguishes convolutional coding generally from alternative coding schemes such as, for example, block coding, in which a small number of message bits is converted to a redundant block codeword and several such block codewords are transmitted to convey the whole message. A general description of known convolutional coding techniques is given below as an aid to understanding the background of the present invention.
An example of convolutional coding will now be discussed in connection with FIG. 1. Illustrated in FIG. 1 is a transmitter 20 having a convolutional encoder 22 consisting of a shift register 24 through which bits of information to be encoded are shifted. The shift register holds a limited number L of bits, the number L being known as the constraint length of the code because the code is constrained to be considered L bits at a time. At any instant, the bits in the shift register 24, which may be labeled B.sub.1, B.sub.2, B.sub.3, B.sub.4, . . . , B.sub.L, are applied to a combinatorial logic network 26 that generates two or more different Boolean combinations of the bits. As illustrated by FIG. 1, the bits in the shift register 24 may be provided by a CRC error detection generator 28 that receives message information to be transmitted and that generates and appends to the message check bits as described above.
The combinations generated by the network 26 are the parity bits, which are described above and which may be designated P.sub.1, P.sub.2, . . . , P.sub.r. The parity bits are transmitted over a communication channel to a receiver 30 having a decoder 32 that converts them back into the data bits B.sub.1, B.sub.2, B.sub.3, B.sub.4 , . . . , B.sub.L, and eventually the message information that was transmitted.
It is to be understood that combinatorial logic network 26 as shown in FIG. 1, may alternatively be implemented as a look-up table comprising 2.sup.L entries stored in a conventional memory. The patterns of the L-bit shift register 24 contents B.sub.1, B.sub.2, B.sub.3, B.sub.4, . . . , B.sub.L would then address respective entries in the look-up table, which produces the characteristic sets of parity bits P.sub.1, P.sub.2, . . . , P.sub.r. The Boolean combinations of the patterns of the bits in the shift register 24 are thus stored in the look-up table rather than generated by the logic network.
If two parity bits are generated for each shift of the bits through the shift register 24, the code is known as a rate 1/2 code, with twice as many parity bits as original data bits being transmitted. If the rate of transmission is fixed, the time required to transmit such parity bits is twice as long as the time required to transmit the original data bits. More generally, if r parity bits are generated on every shift, the code is known as a rate 1/r code. Typically, the parity bit transmission rate is adopted to be r times the message information bit rate.
For example, the Boolean combination equations for generating the parity bits of a rate 1/2 code having a constraint length of five might be: EQU P.sub.1 =B.sub.1 +B.sub.2 +B.sub.3 +B.sub.4 +B.sub.5 EQU P.sub.2 =B.sub.1 +B.sub.4 +B.sub.5
where "+" represents modulo-2 addition. It will be recognized that modulo-2 addition is logically equivalent to the exclusive-OR operation because 0+0 =0; 0 +1= 1+0=1; and 1+1=0.
As noted above, r times more parity bits than input data bits are produced for a rate 1/r code, and, if all parity bits are transmitted, an r-times redundancy has been provided to combat errors. It will, however, be appreciated that it is not necessary to transmit all of the parity bits. If the transmitter and receiver have previously agreed on some regular method of determining which parity bits are not transmitted, the code is then known as a punctured convolutional code. Punctured codes typically result in coding rates m/r, such as 13/29, where adaptation to a transmission rate that is r/m times the message information bit rate is required.
Tables of parity equations for various code rates and constraint lengths that result in optimum codes are published in the technical literature. See, e.g., G. Clarke, Jr., and J. Cain, Error-Correction Coding for Digital Communications, Appendix B, Plenum Press, New York (1981).
The known methods for decoding convolutional codes include threshold decoding, Sequential Maximum Likelihood Sequence Estimation (SMLSE), and the stack algorithm. The SMLSE technique is commonly known as the Viterbi algorithm, which is described in the literature including D. Forney, "The Viterbi Algorithm", Proc. IEEE, Vol. 61, pp. 268-278 (Mar., 1973). A description of decoding methods may be found in the Clarke and Cain text cited above.
The operation of an SMLSE convolutional decoding algorithm is illustrated by FIG. 2 for a rate 1/2 code having a constraint length of five. In the SMLSE decoder, a plurality of electronic storage elements 33, 34, 35 are arranged in groups called states, and the number of states is 2.sup.L-1, where L is the constraint length of the code to be decoded. The storage elements hold at least two different types of information, i.e., bit histories in elements 33 and path metrics in elements 34 associated with the states. In addition, state numbers associated with the states may be stored in elements 34 as binary bit patterns-of L--1 bits each.
A path metric may be considered a confidence factor representing the degree of correlation between a postulated bit sequence and an actual (e.g., received) bit sequence. To the extent that the postulated and actual bit sequences agree, the path metric is smaller and the confidence associated with that postulated bit sequence is greater. It will be understood that "postulated bit sequence", or simply "postulate", refers generally to any hypothetical bit sequence having some probability of being the actual bit sequence of interest. A postulate thus can represent message information bits, parity bits, or other codewords.
An important part of most SMLSE decoders is a "copy" 38 of the encoding algorithm. For the example communication system depicted in FIG. 1, the copy 38 could be an L-bit shift register and a combinatorial logic network that implements the equations used in the encoder 22 to generate the parity bits P.sub.1, P.sub.2, . . . , P.sub.r. Alternatively, the copy 38 could be an L-bit shift register and a 2.sup.L -entry look-up table stored in an electronic memory. In either case, 2.sup.L postulates are generated by the copy 38 and compared directly to the received parity bit stream by a comparator 39.
The (L-1)-bit state numbers in storage elements 34 represent all but one bit of the possible contents of the encoding shift register 24. The L-th bit represents the next bit to be decoded, and can be either ZERO or ONE. Both possibilities are tested in conjunction with all possible combinations of the other-bits represented by the state numbers. Thus, all 2.sup.L possible bit combinations are tested by the decoder, and a running confidence factor, the path metric 35, is stored for evaluating the correlation between the postulated bit sequence and the received parity bit sequence.
The steps of the SMLSE algorithm are generally as follows for the rate 1/2 code having a constraint length of five.
Step 1. For the first state, numbered 0000, it is postulated that the new bit is also a ZERO. The postulate 00000 is thus applied to the copy 38 to obtain the two parity bits P.sub.1 (00000) and P.sub.2 (00000) that would be expected. In this way, the postulate information is encoded using the same parity equations that were used in the encoder 22 shown in FIG. 1.
Step 2. The actual parity bits received P.sub.1 (actual) and P.sub.2 (actual) are compared with the postulated parity bits P.sub.1 (00000) and P.sub.2 (00000) by the comparator 39. The comparison has one of the following results: a match for both bits; a match for one of the two bits and a mismatch for the other of the two bits; or a mismatch for both bits. If both P.sub.1 (00000) and P.sub.2 (00000) match the actual parity bits received P.sub.1 (actual) and P.sub.2 (actual), the value ZERO is added by an adder 36 to the path metric that is associated with the state 0000 and that may be represented by Gp=(0000). Similarly, if there is only a single match, the value one is added to Gp=(0000). If neither P.sub.1 (00000) nor P.sub.2 (00000) match the actual parity bits received P.sub.1 (actual) and P.sub.2 (actual), the value two is added to Gp=0000). In this way, the path metric value for any given state represents the cumulative mismatch between the postulated and actual bit sequences for the particular state. The larger the cumulative mismatch for a state, the larger the path metric value and the smaller the running confidence factor for that state.
Step 3. Steps 1 and 2 are repeated for state 1000. With the new fifth bit postulated to be a ZERO, the pattern 10000 is applied to the copy 38, and its output bits P.sub.1 (10000) and P.sub.2 (10000) are compared to the actual received bits P.sub.1 (actual) and P.sub.2 (actual). The path metric for state 1000, designated Gp=(1000), is updated as in step 2 based upon comparisons of P.sub.1 (actual) and P.sub.2 (actual) with P.sub.1 (10000) and P.sub.2 (10000).
Step 4. The updated path metrics for states 0000 and 1000, i.e., Gpm(0000) and Gp=(1000), are compared by a comparator 37. Whichever state has the lower path metric, and hence the lesser mismatch becomes the new state 0000 when the bit patterns 10000 and 00000 produced by the copy 38 are left-shifted one bit position and the leftmost bit shifts over into the respective bit history in storage elements 33, leaving 0000 in both cases.
Thus, either of the states 1000 or 0000 can be the predecessor to the next state 0000 in the case where the new bit is a 0. Depending on which state survives because it has the lowest path metric, the leftmost bit that drops out of the encoder copy 38 pattern to become the rightmost bit of the bit-history 33 for the next state 0000 will be either a 0 or a 1. Moreover, the other corresponding bits in the new bit-history memory 33 are copied over from the surviving selected state, overwriting the bits of the non-survivor, the state that was not selected. For example, as shown in FIG. 3, if the path metric Gp=(1000) is 1.8 and the path metric Gpm(0000) is 9.5, state 1000 is selected to survive and the left-shifted bits 10110111 are overwritten into the bit-history 33 for the new state 0000.
Step 5. Steps 1-4 are repeated with the postulate that the new bit is a ONE. The postulates 00001 and 10001 for the actual received bits are thus respectively applied to the copy 38 to obtain the pairs of parity bits, P.sub.1 (00001), P.sub.2 (00001) and P.sub.1 (10001), P.sub.2 (10001), that would be expected. These parity bit pairs are compared with the actual received parity bits P.sub.1 (actual) and P.sub.2 (actual), leading to updated path metrics Gp=(0000) and Gp=(1000) which are then compared. This results in a new state 0001 which also has possible predecessor states 0000 and 1000.
Step 6. Steps 1-5 are repeated for every other pair of predecessor states: 0001 and 1001 (resulting in new states 0010 and 0011); 0010 and 1010 (resulting in new states 0100 and 0101); 0011 and 1011 (resulting in new states 0110 and 0111); 0100 and 1100 (resulting in new states 1000 and 1001); 0101 and 1101 (resulting in new states 1010 and 1011); 0110 and 1110 (resulting in new states 1100 and 1101); and 0111 and 1111 (resulting in new states 1110 and 1111).
At the end of the above six steps, two actual received parity bits have been processed and one new decoded bit has been shifted into all of the bit history storage elements 33. These memorized patterns are candidates for the final SMLSE sequence. Because of the way bit histories overwrite other bit histories, when one of a pair of states is selected to survive, the older bits in the storage elements 33 tend towards agreement. If the oldest bits in all bit histories agree, they may be removed as a final decision and the bit history storage elements 33 shortened by one bit.
The algorithm for other rate codes, such as rate 1/4, proceeds similarly although four parity bits would be generated by each postulate and compared with four received bits, generating possible increments to the cumulative path metrics of ZERO, one, two, three, or four mismatches.
In another variation of the known algorithm, the received parity bits are characterized not just by their bit polarities, but by a magnitude or quality measure representing the degree of "ONE-ness" or "ZERO-ness". When a mismatch with a locally predicted postulate parity bit is detected, the path metric is penalized by a greater amount if the received bit quality is high and there is therefore less doubt that its sign was in fact correct, than if the quality is low and the received bit polarity was doubtful. This "soft" decoding as opposed to "hard" decoding ideally uses a "soft" bit quality measure that is related to -LOG(Probability) where "probability" is the probability that the bit polarity is correct. When this logarithmic measure is used, the cumulative metric then represents minus the logarithm of the product of all the bit probabilities. The state and bit-history sequence then having the smallest cumulative metric represents the sequence having the highest probability of being right. Usually, the noise is assumed Gaussian, in which case the penalty term can be shown to be proportional to the square of the bit amplitude. The penalization for a mismatch between a locally predicted postulate bit and a received high quality bit may be effected by adding a term proportional to 1/(-LOG(Probability)) to the cumulative logarithmic measure when a mismatch is detected. Such an addition can only substantially affect the measure whenever the probability is high that the received bit polarity is correct and yet a mismatch is detected nonetheless.
Such convolutional coders and decoders can also be built to work with non-binary symbols such as ternary or quaternary symbols.
An SMLSE Viterbi decoder determines the sequence of data bits that most closely explain the received signal. The Viterbi algorithm allows the best sequence to be determined successively thus avoiding the need to test all two-to-the-power of N possible sequences. To establish a starting point for the successive determinations, in some coding schemes, the encoder is initialized to a known starting state before feeding in data bits. In this case, there is only one allowed initial state for the decoder. The number of states then doubles at each successive step up to two to the power of the (code constraint length -1). After this point, the number of states doubles each time a new unknown bit is postulated but immediately halves again due to an earlier-hypothesized bit now being decided to one of two specific values. The number of states thus remains constant until the last unknown data bit is hypothesized. Then, in some coding schemes, known bits are fed into the encoder to flush through the last data bit. When no more data bits are left in the encoder, its output does not depend on data and need not be transmitted. The receiver decoder knows a priori what this terminal state will be and each time one more undecided data bit is flushed out of the encoder, the number of possible remaining states halves until it becomes a single state. This method of terminating a convolutional block encoder by up and down tapering from a single starting state to a single end state is called "using tail bits". The known bits in the encoder at the beginning (or used to flush out the last data bit at the end) give rise to extra transmitted bits. These additional bits that are just used to initialize and terminate the encoder may be avoided by using the alternative method known as tail biting. In tail biting, a number L of data bits is used to initialize the encoder, where L is the number of internal memory elements in the encoder also known as the constraint length. The number of possible starting states is thus 2.sup.L.
The decoder in this instance assumes all starting states to be possible, not just a single state. The first coded bits transmitted that depend on the first L bits are compared with corresponding predictions at the receiver and a mismatch or path metric is computed for each possibility. Then, one data bit is shifted out of the encoder and a new data bit is shifted in. This halves the number of states but due to the new bit being unknown, the number of predictions and path metric calculations doubles to the same number as before. A Viterbi MSLE machine can be regarded as beginning and ending a cycle at the point where the number of states has halved, and just before a new bit is hypothesized. That way, the number of states and path metrics that have to be stored is 2.sup.(L-1) rather than 2.sup.L although the number of path metric computations is always 2.sup.L. Using tail biting, after feeding in the last data bit to the encoder, it is flushed through by feeding in the first L-1 data bits again, effectively completing the circle. The receiver can continue around the circle by processing the first signal samples again and continuing until no further change in the decoded output is observed. Alternatively, a tail-biting decoder can continue for a fixed number or fraction of a revolution, at which point the state that has the lowest cumulative path metric is chosen.
Appending a CRC code, as described above, does not come free--it expands the number of coded bits transmitted by the number of CRC bits appended multiplied by the rate of the code. The energy for transmitting the extra bits created by adding the CRC code should be subtracted from the energy used to transmit data if comparison between systems with and without CRC are to be on the basis of equal energy transmitted. Thus, the use of a CRC will generally result in a higher error rate than if no CRC had been used. The errors are, however, detectable.
Prior art methods of adding bits to data to be transmitted, such as the using tail bits method and the CRC code have the further disadvantage of adding additional bits for transmission, with the related costs in energy and transmission rate requirements, generally without providing any improvement in the performance of the error correction decoding operation at the receiving communication system. Determinate bit error correction coding systems may provide improved error correction decoding but generally are not designed to provide for error detection. In addition, the CRC error detection method generally requires completion of error correction decoding before testing for error detection.